package ljl.alg.wangzheng_camp.round1.sort;

import java.util.Arrays;

/**
 * 这个题真的难兄弟们
 * 不好写的
 *
 * 主要是不会归并排序
 * 其次，就算会归并，我也不好做这个题
 *
 * */
public class _offer51_reversed_pair_count {
    
    /*
    * 这不对那不对
    * 哪不对？
    * 最烦这种，这不对那不对，有事说事，对不对？
    * */
    class dont_get_it {
        public int reversePairs(int[] nums) {
            return merge(nums, new int[nums.length], 0, nums.length - 1);
        }
    
        int merge(int[] nums, int[] tmp, int from, int to) {
            if (from >= to) return 0;
            int m = (from + to) >>> 1;
            int res = merge(nums, tmp, from, m) + merge(nums, tmp, m + 1, to);
            System.arraycopy(nums, from, tmp, from, to - from + 1);
        
            int i = from, j = m + 1;
            for (int k = from; k <= to; k++) {
                if (i > m) nums[k] = tmp[j++];
                else if (j > to || tmp[i] <= tmp[j]) nums[k] = tmp[i++];
                else {
                    res += m - i + 1;
                    nums[k] = tmp[j++];
                }
            }
            return res;
        }
    }
    
    class try2 {
        public int reversePairs(int[] nums) {
            int n = nums.length;
            int[] tmp = Arrays.copyOf(nums, n);
            Arrays.sort(tmp);
            for (int i = 0; i < nums.length; i++) {
                // 不可以是 0 的
                nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;
            }
            
            BitTree tree = new BitTree(n);
            int res = 0;
            for (int i = n - 1; i >= 0 ; i--) {
                res += tree.ask(nums[i] - 1);
                tree.update(nums[i]);
            }
            return res;
        }
        
        public static class BitTree {
            public final int[] tree;
            public final int n;
            BitTree(int n) {
                tree = new int[n + 1];
                this.n = n;
            }
            int lowestBit(int x) {
                return x & -x;
            }
            void update(int i) {
                for (;i <= n ; i += lowestBit(i)) {
                    tree[i]++;
                }
            }
            int ask(int i) {
                int res = 0;
                for (; i > 0 ; i -= lowestBit(i)) {
                    res += tree[i];
                }
                return res;
            }
        }
    }
}
